# -*- coding: utf-8 -*-

"""剑指 Offer 20. 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：
    若干空格
    一个 小数 或者 整数
    （可选）一个 'e' 或 'E' ，后面跟着一个 整数
    若干空格

小数（按顺序）可以分成以下几个部分：
    （可选）一个符号字符（'+' 或 '-'）
    下述格式之一：
    至少一位数字，后面跟着一个点 '.'
    至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
    一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：
    （可选）一个符号字符（'+' 或 '-'）
    至少一位数字

部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

示例 1：
输入：s = "0"
输出：true

示例 2：
输入：s = "e"
输出：false

示例 3：
输入：s = "."
输出：false

示例 4：
输入：s = "    .1  "
输出：true

提示：
1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。"""

class Solution:
    """o020_is_number.py版本中用语法分析中的回溯下降算法实现了判断，但耗时只超过了30%多的提交。
    在学习题解之后，发现有限状态自动机机(determined finite state auto)的另外一种用法，有限的状态，从初始状态，经过确定的状态转移规则，看是否能达到终结状态

    状态（一个常用的技巧是，用「当前处理到字符串的哪个部分」当作状态的表述）：
        head_space
        sign
        int
        int_dot
        null_dot
        small_int
        e
        exp_sign
        exp_int
        tail_space
    
    ！！！在草稿纸上画出状态转移图

    状态转移图以字典表的形式实现
    """

    dfs = {
        'HeadSpace': {
            ' ': 'HeadSpace',
            '+': 'Sign','-': 'Sign',
            '0': 'Int','1': 'Int','2': 'Int','3': 'Int','4': 'Int','5': 'Int','6': 'Int','7': 'Int','8': 'Int','9': 'Int',
            '.': 'NullDot',
        },

        'Sign': {
            '0': 'Int','1': 'Int','2': 'Int','3': 'Int','4': 'Int','5': 'Int','6': 'Int','7': 'Int','8': 'Int','9': 'Int',
            '.': 'NullDot',
        },
        
        'Int': {
            '0': 'Int','1': 'Int','2': 'Int','3': 'Int','4': 'Int','5': 'Int','6': 'Int','7': 'Int','8': 'Int','9': 'Int',
            '.': 'IntDot',
            'E': 'E','e': 'E',
            ' ': 'TailSpace',
        },
        
        'IntDot': {
            '0': 'SmallInt','1': 'SmallInt','2': 'SmallInt','3': 'SmallInt','4': 'SmallInt','5': 'SmallInt','6': 'SmallInt','7': 'SmallInt','8': 'SmallInt','9': 'SmallInt',
            'E': 'E','e': 'E',
            ' ': 'TailSpace',
        },
        
        'NullDot': {
            '0': 'SmallInt','1': 'SmallInt','2': 'SmallInt','3': 'SmallInt','4': 'SmallInt','5': 'SmallInt','6': 'SmallInt','7': 'SmallInt','8': 'SmallInt','9': 'SmallInt',
        },

        'SmallInt': {
            '0': 'SmallInt','1': 'SmallInt','2': 'SmallInt','3': 'SmallInt','4': 'SmallInt','5': 'SmallInt','6': 'SmallInt','7': 'SmallInt','8': 'SmallInt','9': 'SmallInt',
            'E': 'E','e': 'E',
            ' ': 'TailSpace',
        },
        
        'E': {
            '+': 'ExpSign','-': 'ExpSign',
            '0': 'ExpInt','1': 'ExpInt','2': 'ExpInt','3': 'ExpInt','4': 'ExpInt','5': 'ExpInt','6': 'ExpInt','7': 'ExpInt','8': 'ExpInt','9': 'ExpInt',
        },
        
        'ExpSign': {
            '0': 'ExpInt','1': 'ExpInt','2': 'ExpInt','3': 'ExpInt','4': 'ExpInt','5': 'ExpInt','6': 'ExpInt','7': 'ExpInt','8': 'ExpInt','9': 'ExpInt',
        },
        
        'ExpInt': {
            '0': 'ExpInt','1': 'ExpInt','2': 'ExpInt','3': 'ExpInt','4': 'ExpInt','5': 'ExpInt','6': 'ExpInt','7': 'ExpInt','8': 'ExpInt','9': 'ExpInt',
            ' ': 'TailSpace',
        },
        
        'TailSpace': {
            ' ': 'TailSpace',
        },
    }

    def isNumber(self, s: str) -> bool:
        s += ' '
        state = 'HeadSpace'
        for chr in s:
            next_state = self.dfs.get(state).get(chr)
            if not next_state:
                return False
            state = next_state
        
        return state == 'TailSpace'


if __name__ == '__main__':
    so = Solution()
    for s in ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123 "]:
        print(so.isNumber(s))
    for s in ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4", "1 "]:
        print(so.isNumber(s))

